#include "project5.h"
#include <list>
#include <fstream>
#include <iostream>
#include <string>
#include <time.h>
using namespace std;
Graph loadGraph(void)
{
	int numVertex = 0;
	int numEdges = 0;
	ifstream file;
    string fileName = "swa.txt";
	file.open(fileName.c_str());
	if(!file.is_open()) 
	{	
        cout << "Could not open:" << fileName << endl;
	}
    Graph graph;
    graph.Vertices;
    file >> numVertex;
	file >> numEdges;
    int id = 0;
    for (int i = 0; i < numVertex; i++)
    {
        Vertex vertex;
        vertex.ID = i;
        file >> vertex.Code;
        graph.Vertices.push_back(vertex);
    }
    for (int i = 0; i < numEdges; i++)
    {
        Edge edge;

        file >> edge.v1.Code;
        for(VertexSet::const_iterator it = graph.Vertices.begin(); it != graph.Vertices.end(); ++it)
        {
            if(strcmp(it->Code, edge.v1.Code) == 0)
            {
                edge.v1.ID = it->ID;
            }
        }

        file >> edge.v2.Code;
        for (VertexSet::const_iterator it = graph.Vertices.begin(); it != graph.Vertices.end(); ++it)
        {
            if(strcmp(it->Code, edge.v2.Code) == 0)
            {
                edge.v2.ID = it->ID;
            }
        }
        graph.Edges.push_back(edge);
    }
    if ((graph.NumEdges() != numEdges) || (graph.NumVertices() != numVertex))
    {
        cout << "Incorrectly loaded graph" << endl;
        
    }  
    
    return graph;
}

UIntSet VertexCover(Graph& g)
{
    UIntSet best;    
    uint n = g.NumVertices();
    uint lastBitMask = (1 << n) - 1;
    bool XisCover = true;
    bool IIsCover = false;
    for (uint bits = 0; bits <= lastBitMask; ++bits)
    {
        UIntSet X;
        for(uint i = 0; i < n; ++i)
        {
            if (bits & (1 << i))
            {                
                X.push_back(i);
            }
        }

        if ((X.size() == 1) && (X.front() == 3))
        {
            int stupid = 0;
            stupid = 3;
        }
        XisCover = true;
        for (uint i = 0; i < n; ++i)
        {
            IIsCover = false;
            for (UIntSet::const_iterator j = X.begin(); j != X.end(); ++j)
            {
                if (i != *j)
                {
                    if (g.ContainsEdge(i, *j))
                    {
                        IIsCover = true;
                        break;
                    }
                }
            }
            if (IIsCover == false)
            {
                XisCover = false;
                break;
            }            
        }
        
        
        if (XisCover == false)
        {
            continue;
        }
        if (best.size() == 0)
        {
            best = X;
        }
        else if (X.size() < best.size())
        {
            best = X;
        }
    }
    return best;
}

bool Graph::ContainsEdge( uint i, uint j )
{    
    Vertex vi, vj;
    // get the ith vertex
    uint c;
    c = 0;
    for (VertexSet::const_iterator it = Vertices.begin(); it != Vertices.end(); ++c, ++it)
    {
        if (c == i)
        {
            vi = *it;
        }
    }
    // get the jth vertex    
    c = 0;
    for (VertexSet::const_iterator it = Vertices.begin(); it != Vertices.end(); ++c, ++it)
    {
        if (c == j)
        {
            vj = *it;
        }
    }

    // see if the graph has an edge between the ith and jth vertex
    for (EdgeSet::const_iterator it = Edges.begin(); it != Edges.end(); ++it)
    {
        uint it1 = it->v1.ID;
        uint it2 = it->v2.ID;
        if (((it1 == vi.ID) && (it2 == vj.ID)) ||
            ((it1 == vj.ID) && (it2 == vi.ID))
            )
        {
            return true;
        }
    }
    return false;
}

void Graph::Print()
{
    for (VertexSet::const_iterator it = Vertices.begin(); it != Vertices.end(); ++it)
    {
        cout << "Vertex: " << it->ID << " " << it->Code << endl;
    }

    uint i = 0;
    for (EdgeSet::const_iterator it = Edges.begin(); it != Edges.end(); ++it, ++i)
    {
        cout << "Edge: " << i << endl;
        cout << "Vertex 1: " << it->v1.ID << " " << it->v1.Code << endl;
        cout << "Vertex 2: " << it->v2.ID << " " << it->v2.Code << endl;
    }
}

VertexSet approxVertexCover( Graph graph )
{
	VertexSet cover;
	while (graph.NumEdges() > 0)
	{
		int set = 1;
		Edge edge = graph.Edges.front();
		cover.push_back(edge.v1);
		cover.push_back(edge.v2);
		Graph newGraph;
        for (EdgeSet::const_iterator f = graph.Edges.begin(); f != graph.Edges.end(); ++f)
		{
			if ((f->v1.ID == edge.v1.ID) || (f->v2.ID == edge.v1.ID))
			{
				//graphCopy.Edges.remove(edge);
				set = 0;
			}
			if ((f->v1.ID == edge.v2.ID) || (f->v2.ID == edge.v2.ID))
			{
				//graphCopy.Edges.remove(edge);
				set = 0;
			}
			if ( set )
			{
				newGraph.Edges.push_back(*f);
			}
		}
		graph = newGraph;
		
	}
	return cover;
}

void display(Graph& original, VertexSet& vertices, long time, VertexSet& vertices2, long time2 )
{
	cout << "=============================================================\n";
	cout << "Subgraph for  n=" << original.NumVertices() << " has " << original.NumVertices() << " vertices and " << original.NumEdges() << " edges.\n";
	cout << "Using only airport codes ";
	for (VertexSet::const_iterator it = original.Vertices.begin(); it != original.Vertices.end(); ++it)
	{
		cout << it->Code << " ";
	}
	cout << endl;
	// Exhaustive search display
	cout << "- Exhaustive Search - \n";
	cout << vertices.size() << " elements: ";
	for (VertexSet::const_iterator it = vertices.begin(); it != vertices.end(); ++it)
	{
		cout << it->Code << "(" << it->ID << ") ";
	}
	cout << "Elapsed time = " << time << " seconds\n";

	// 2-approximation display
	cout << "- 2-approximation - \n";
	cout << vertices2.size() << " elements: ";
	for (VertexSet::const_iterator it = vertices2.begin(); it != vertices2.end(); ++it)
	{
		cout << it->Code << "(" << it->ID << ") ";
	}
	cout << "Elapsed time = " << time2 << " seconds\n";
}
Graph CreateSubGraph( Graph& g, uint numVertices )
{
    Graph newG;
    uint i = 0;
    // Add the vertices to the new graph    
    for (VertexSet::const_iterator it = g.Vertices.begin(); i < numVertices; ++it, ++i)
    {
        newG.Vertices.push_back(*it);
    }

    // brute force subgraph
    // iterate through every edge in big graph
    for (EdgeSet::const_iterator eit = g.Edges.begin(); eit != g.Edges.end(); ++eit)
    {
        uint vertContain = 0;
        // iterate through every vertex in sub graph
        for (VertexSet::const_iterator vit = newG.Vertices.begin(); vit != newG.Vertices.end(); ++vit)
        {
            // if a vertex in sub graph is in the edge of the big graph, 
            if(((*eit).v1.ID == (*vit).ID || (*eit).v2.ID == (*vit).ID))
            {
                // increment that we found a match
                vertContain++;
            }
        }
        // need two vertices's to make an edge
        if (vertContain == 2)
        {
            newG.Edges.push_back(*eit);
        }
    }

    VertexSet newVertices;
    // now that we have all the edges, get a list of all unique vertices from those edges, and only have those vertices which are a part of a edge in the vertices list

    // iterate through all the vertices
    for (VertexSet::const_iterator vit = newG.Vertices.begin(); vit != newG.Vertices.end(); ++vit)
    {
        // check to make sure that vertices is a part of at least one edge in our new graph       
        for (EdgeSet::const_iterator eit = newG.Edges.begin(); eit != newG.Edges.end(); ++eit)
        {
            if ((vit->ID == eit->v1.ID) || (vit->ID == eit->v2.ID))
            {
                newVertices.push_back(*vit);
                break;
            }
        }
    }
    newG.Vertices = newVertices;
    
    return newG;    
}

void RunVertexCoverTest(Graph graph, uint n )
{    
    long startTime, endTime, exhaustiveRunTime, approxRunTime;

    Graph subGraph = CreateSubGraph(graph, n );    
    subGraph.Print();
    startTime = clock();
    UIntSet exhaustiveVC = VertexCover(subGraph);
    endTime = clock();
    exhaustiveRunTime = endTime - startTime;
	VertexSet converted = convertGraph(subGraph, exhaustiveVC);

    startTime = clock();
    VertexSet approxVC; //= approxVertexCover(subGraph);
    endTime = clock();
    approxRunTime = endTime - startTime;

    display(subGraph, converted, exhaustiveRunTime, approxVC, approxRunTime);       
}

VertexSet convertGraph( Graph graph, UIntSet index )
{
	VertexSet converted;
	for (UIntSet::const_iterator it = index.begin(); it != index.end(); ++it)
	{
		int i = 0;
		for (VertexSet::const_iterator vit = graph.Vertices.begin(); vit != graph.Vertices.end(); ++vit, i++)
		{
			if((*it) == i)
			{
				converted.push_back(*vit);
			}
		}
	}
	return converted;
}